一个关于并查集的问题

首先,其实我去年就在讨论区问过这个问题的,但是……没人理我……

就是这么个东西,一个普通的,带路径压缩的并查集

int n, f[N], counter = 0;
int fa(int x) {
	counter++;
	return f[x] == x ? x : f[x] = fa(f[x]); 
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		f[i] = f[i-1] = i;
		fa(rand() % i);
	}
	printf("%d\n", counter);
}

其中rand()返回的是均匀随机数,求输出的counter的数学期望

根据一波打表找规律发现答案是

ni=1n11in\sum_{i=1}^{n-1}\frac{1}{i}

证明:

定义合法树为:每个节点的编号均小于其父节点编号的树,那么:

  1. 对于每个随机序列,按照以上代码生成的树都是合法树
  2. 不同的随机序列有(n1)!(n-1)!
  3. 不同的合法树有(n1)!(n-1)!
  4. 对于每个合法树,都存在一个随机序列,使得按照以上代码能生成该树

简述下第四条的构造方法,对于一棵合法树,每次删除根节点,则剩下的子树里编号最小的点就是序列的最后一个点。把剩下的子树按照节点编号大小排序连成一条链,那么对该树上刚才找到的点进行路径压缩可以得到原树(如下图),且显然这样做剩下的树仍然是合法树,循环下去求即可

结合以上四条,可得:随机序列和合法树是一一对应的

那么我们要求的就是所有合法树上平均的答案,很容易递推

f(n)f(n)counter的期望,h(n)h(n)为点数为nn的合法树所有节点深度的平均值(根节点深度为11),则有递推式

f(1)=0f(1)=0

h(1)=1h(1)=1

f(n)=1+f(n1)+h(n1)f(n)=1+f(n-1)+h(n-1)

h(n)=h(n1)+1nh(n)=h(n-1)+\frac{1}{n}

然后随便推两下就能求出来了

证毕